# 给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
#
#  有效的 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
#
#  例如："0.1.2.201" 和 "192.168.1.1" 是 有效的 IP 地址，但是 "0.011.255.245"、"192.168.1.312"
#  和 "192.168@1.1" 是 无效的 IP 地址。
#
#
#
#  示例 1：
#
#  输入：s = "25525511135"
# 输出：["255.255.11.135","255.255.111.35"]
#
#
#  示例 2：
#
#  输入：s = "0000"
# 输出：["0.0.0.0"]
#
#
#  示例 3：
#
#  输入：s = "1111"
# 输出：["1.1.1.1"]
#
#
#  示例 4：
#
#  输入：s = "010010"
# 输出：["0.10.0.10","0.100.1.0"]
#
#
#  示例 5：
#
#  输入：s = "101023"
# 输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
#
#
#
#
#  提示：
#
#
#  0 <= s.length <= 3000
#  s 仅由数字组成
#
#  Related Topics 字符串 回溯算法
#  👍 402 👎 0


# leetcode submit region begin(Prohibit modification and deletion)
from typing import List


class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        def dfs(s, depth, tmp, res):

            if depth > 4:
                res.append(tmp[:len(tmp) - 1])
                return

            if len(s) == 0:
                return

            # ip 地址每一节最多3个数字
            for i in range(1, min(len(s), 3) + 1):

                substr = s[:i]

                if len(substr) > 1 and substr[0] == '0':
                    return

                elif int(substr) > 255:
                    return

                # 剩余数字过多
                elif (4 - depth) * 3 < len(s) - len(substr):
                    continue
                else:
                    dfs(s[i:], depth + 1, tmp + substr + ".", res)

        res = []
        dfs(s, 1, "", res)
        return res

    def restoreIpAddresses1(self, s: str) -> List[str]:

        """
        复原ip ，一共分为 4 段 ，每段的数字不能 大于 255 ，也不能 0 开头

        :param s:
        :return:
        """

        def dfs(s, res, tmp, depth, start):
            if depth > 4:
                # 去除最后的 "."
                res.append(tmp[:len(tmp) - 1])
                return

            # 最多三个数字
            for i in range(1, min(len(s) - start, 3) + 1):
                substr = s[start:start + i]

                # 有零出现，
                if i > 1 and substr[0] == '0':
                    return

                # 大于 255 ，也不行
                if int(substr) > 255:
                    return

                # 剩余位数过多，这段截长一点，进入下一次循环
                if len(s) - start - i > (4 - depth) * 3:
                    continue
                else:
                    dfs(s, res, tmp[:] + substr + ".", depth + 1, start + i)

        # leetcode submit region end(Prohibit modification and deletion)

        res = []

        dfs(s, res, "", 1, 0)

        return res


print(Solution().restoreIpAddresses("25525511135"))

print(Solution().restoreIpAddresses1("25525511135"))
